struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
#include <queue>
// BM12 单链表的排序
struct compare
{
    bool operator()(ListNode *a, ListNode *b)
    {
        return a->val > b->val;
    }
};
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode *sortInList(ListNode *head)
    {
        std::priority_queue<ListNode *, std::vector<ListNode *>, compare> mypq;
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        // write code here
        // 边界条件
        if (head == nullptr || head->next == nullptr)
            return head;
        // 构建小顶堆
        while (head)
        {
            mypq.push(head);
            head = head->next;
        }
        while (!mypq.empty())
        {
            ListNode *top = mypq.top();
            mypq.pop();
            // 成环了
            cur->next = top;
            cur = cur->next;
            // 破环环
            cur->next = nullptr;
        }
        return dummy->next;
    }

    // 复习堆的生成 见03struct 链表排序
// 方法二 归并排序
    ListNode *sortInList2(ListNode *head)
    {
        // 边界条件
        if (head == nullptr || head->next == nullptr)
            return head;
        // 方法1 归并排序
        // 1.找到中点并分割链表 2.各段排序 3.合并
        auto mid = findMid(head);
        return merge(sortInList2(head), sortInList2(mid));
    }
    // 定义寻中点函数
    ListNode *findMid(ListNode *head)
    {
        // 快慢指针 快指针速度是慢指针的两倍
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast != nullptr && fast->next != nullptr)
        {
            pre = pre->next;
            slow = slow->next;
            fast = fast->next->next;
        }
        // 切断链表
        pre->next = nullptr;

        return slow;
    }
    // 定义合并函数
    ListNode *merge(ListNode *left, ListNode *right)
    {
        if (left == nullptr)
            return right;
        if (right == nullptr)
            return left;
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (left != nullptr && right != nullptr)
        {
            if (left->val < right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        // 合并剩余部分
        if (left != nullptr)
            cur->next = left;
        else
            cur->next = right;
        return dummy->next;
    }

// 方法三 快速排序 选定一个基数，然后比较大小，小的放在左边，大的放在右边，然后递归
    ListNode *sortInList3(ListNode *head)
    {
        // 边界条件
    if (head == nullptr || head->next == nullptr)
        return head;
    quickSort(head, nullptr);
    }
    ListNode* partition(ListNode* head, ListNode* end){
        int pivot = head->val;
        ListNode* p = head;// p指向小于pivot的最后一个节点
        ListNode* q = head->next;//q用于遍历并和pivot比较
        while(q!=end){
            if(q->val<pivot){
                p = p->next;//p指向的是小于pivot的最后一个节点
                std::swap(p->val,q->val);//交换p和q的值
            }
            q = q->next;
        }
        std::swap(p->val,head->val);//交换p和head的值
        return p;//返回pivot的位置

    }
    // 在原始链表中交换值 

    void quickSort(ListNode* head, ListNode* end){
        if(head!=end){
            ListNode* mid = partition(head,end);
            quickSort(head,mid);
            quickSort(mid->next,end);
        }
    }
};